package dynamic;

/**题目：求路径数量
 * 给定一个m*n的矩阵
 * 要求计算从左上角走到右下角一共的走法，要求就是只能向右和向下走
 * @Author Gavin
 * @date 2022.01.09 16:15
 */
public class solution_6 {
    /**
     * 动态规划题目：
     * 需要找到状态和状态方程
     * 我们知道一个m*n的矩阵的左上角到第0行的右边任何列的走法只有一种，
     * 到第0列上面的任何行的走法也只有一种
     * 所以可以得出如下的状态方程：
     * d(0,j)=1
     * d(i,0)=1
     * d(i,j)=d(i-1,j)+d(i,j-1)
     */
    public int solution(int m,int n){
        if(m<1||n<1)return 0;
        //定义一个二维数组用来存遍历值
        int[][] d=new int[m][n];
        //先填充第0行和第0列的初始值为1
        for (int i = 0; i < n; i++) {
            d[0][i]=1;
        }
        for (int i = 0; i < m; i++) {
            d[i][0]=1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                d[i][j]=d[i-1][j]+d[i][j-1];
            }
        }
        return d[m-1][n-1];
    }
}
